//f[n]=2*f[0]+2*f[1]+...+2*f[n-3]+f[n-2]+f[n-1]
//化简得f[n]=f[n-3]+2*f[n-1]
public class Solution790 {
    public int numTilings(int n) {
        int mod=1000000007;
        long[] f=new long[1005];
        f[0]=f[1]=1;
        f[2]=2;
        for (int i=3;i<=n;i++){
            f[i]=((2*f[i-1]%mod)+f[i-3])%mod;
        }
        return (int)f[n];
    }

    public static void main(String[] args) {
        System.out.println(new Solution790().numTilings(5));
    }
}
